Vector Quantization

K-means Clustering를 이용해, 각 cluster의 centroid를 묶어논 Codebook을 만든다.
그리고 각 데이터를 Codebook의 각 Code word(codebook Vector, Centroid)중 가장 Distance가 작은 $k$번째에 대해 해당 code word로 변환시킨다.

즉, $N$개의 데이터가 $K$개의 데이터로 표현되게 되는 Encoding 과정이 된다.

• encoding: $q^t=\arg {\min }_{k}d(\overrightarrow{x^t},\overrightarrow{{\mu }_k})$: $\overrightarrow{{\mu }_k}$는 Centroid, $q^t$는 $k$: index
• decoding: $\overrightarrow{\stackrel{~}{x^t}}=\overrightarrow{{\mu }_{q^t}}$: 해당 $q^t$에 해당하는 $\vec{\mu }$로 복원한다.

이 때, decoding 하는 과정에서 기존의 온전한 데이터로 복원하지 못하므로 Reconstruction Error가 생기게 된다.

Reconstruction error

---

$$E(\{\overrightarrow{{\mu }_k}{\}}_{k=1}^K|D)=\frac{1}{N}\sum _t\Vert \overrightarrow{x^t}-\overrightarrow{{\mu }_{q^t}}{\Vert }_2^2=\frac{1}{N}\sum _t\sum _k{z}_k^t\Vert \overrightarrow{x^t}-\overrightarrow{{\mu }_k}{\Vert }_2^2$$

: when $z_k^t=\{\begin{array}{ll}1& \text{if }k=q^t\\ 0& \text{otherwise}\end{array}$

조정 가능한 대상은 $\overrightarrow{{\mu }_k}$이므로, 이를 최소화 하는 방법은

: 정리하면, $\overrightarrow{{\mu }_k}=\frac{\sum _t{z}_k^t\overrightarrow{x^t}}{\sum _t{z}_k^t}$ : 일 때 error minimize 된다.